{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Course Schedule IV"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #depth-first-search #breadth-first-search #graph #topological-sort"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #深度优先搜索 #广度优先搜索 #图 #拓扑排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: checkIfPrerequisite"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #课程表 IV"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>你总共需要上<meta charset=\"UTF-8\" />&nbsp;<code>numCourses</code>&nbsp;门课，课程编号依次为 <code>0</code>&nbsp;到&nbsp;<code>numCourses-1</code>&nbsp;。你会得到一个数组&nbsp;<code>prerequisite</code> ，其中<meta charset=\"UTF-8\" />&nbsp;<code>prerequisites[i] = [a<sub>i</sub>, b<sub>i</sub>]</code>&nbsp;表示如果你想选<meta charset=\"UTF-8\" />&nbsp;<code>b<sub>i</sub></code> 课程，你<strong> 必须</strong> 先选<meta charset=\"UTF-8\" />&nbsp;<code>a<sub>i</sub></code>&nbsp;课程。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>有的课会有直接的先修课程，比如如果想上课程 <code>1</code>&nbsp;，你必须先上课程 <code>0</code>&nbsp;，那么会以 <code>[0,1]</code>&nbsp;数对的形式给出先修课程数对。</li>\n",
    "</ul>\n",
    "\n",
    "<p>先决条件也可以是 <strong>间接</strong> 的。如果课程 <code>a</code> 是课程 <code>b</code> 的先决条件，课程 <code>b</code> 是课程 <code>c</code> 的先决条件，那么课程 <code>a</code> 就是课程 <code>c</code> 的先决条件。</p>\n",
    "\n",
    "<p>你也得到一个数组<meta charset=\"UTF-8\" />&nbsp;<code>queries</code>&nbsp;，其中<meta charset=\"UTF-8\" />&nbsp;<code>queries[j] = [u<sub>j</sub>, v<sub>j</sub>]</code>。对于第 <code>j</code> 个查询，您应该回答课程<meta charset=\"UTF-8\" />&nbsp;<code>u<sub>j</sub></code>&nbsp;是否是课程<meta charset=\"UTF-8\" />&nbsp;<code>v<sub>j</sub></code>&nbsp;的先决条件。</p>\n",
    "\n",
    "<p>返回一个布尔数组 <code>answer</code> ，其中 <code>answer[j]</code> 是第 <code>j</code> 个查询的答案。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/05/01/courses4-1-graph.jpg\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>numCourses = 2, prerequisites = [[1,0]], queries = [[0,1],[1,0]]\n",
    "<strong>输出：</strong>[false,true]\n",
    "<strong>解释：</strong>课程 0 不是课程 1 的先修课程，但课程 1 是课程 0 的先修课程。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>numCourses = 2, prerequisites = [], queries = [[1,0],[0,1]]\n",
    "<strong>输出：</strong>[false,false]\n",
    "<strong>解释：</strong>没有先修课程对，所以每门课程之间是独立的。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/05/01/courses4-3-graph.jpg\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>numCourses = 3, prerequisites = [[1,2],[1,0],[2,0]], queries = [[1,0],[1,2]]\n",
    "<strong>输出：</strong>[true,true]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<p><meta charset=\"UTF-8\" /></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>2 &lt;= numCourses &lt;= 100</code></li>\n",
    "\t<li><code>0 &lt;= prerequisites.length &lt;= (numCourses * (numCourses - 1) / 2)</code></li>\n",
    "\t<li><code>prerequisites[i].length == 2</code></li>\n",
    "\t<li><code>0 &lt;= a<sub>i</sub>, b<sub>i</sub>&nbsp;&lt;= n - 1</code></li>\n",
    "\t<li><code>a<sub>i</sub>&nbsp;!= b<sub>i</sub></code></li>\n",
    "\t<li>每一对<meta charset=\"UTF-8\" />&nbsp;<code>[a<sub>i</sub>, b<sub>i</sub>]</code>&nbsp;都 <strong>不同</strong></li>\n",
    "\t<li>先修课程图中没有环。</li>\n",
    "\t<li><code>1 &lt;= queries.length &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>0 &lt;= u<sub>i</sub>, v<sub>i</sub>&nbsp;&lt;= n - 1</code></li>\n",
    "\t<li><code>u<sub>i</sub>&nbsp;!= v<sub>i</sub></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [course-schedule-iv](https://leetcode.cn/problems/course-schedule-iv/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [course-schedule-iv](https://leetcode.cn/problems/course-schedule-iv/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['2\\n[[1,0]]\\n[[0,1],[1,0]]', '2\\n[]\\n[[1,0],[0,1]]', '3\\n[[1,2],[1,0],[2,0]]\\n[[1,0],[1,2]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:\n",
    "        res = []\n",
    "        grid = [[0 for _ in range(numCourses)] for _ in range(numCourses)] # 记录从a到b有没有路劲\n",
    "        for a,b in prerequisites:\n",
    "            grid[a][b] = 1\n",
    "        for k in range(numCourses):\n",
    "            for i in range(numCourses):\n",
    "                for j in range(numCourses):\n",
    "                    if i==j:\n",
    "                        grid[i][j] = 1\n",
    "                        continue\n",
    "                    if grid[i][j]!=1:\n",
    "                        if grid[i][k]==1 and grid[k][j]==1:\n",
    "                            grid[i][j]=1\n",
    "        # for start in range(numCourses):\n",
    "        #     for end in range(numCourses):\n",
    "        #         if start==end:\n",
    "        #             grid[start][end]=1\n",
    "        #         if grid[start][end]!=1:\n",
    "        #             for k in range(numCourses):\n",
    "        #                 if grid[start][k]==1 and grid[k][end]==1:\n",
    "        #                     grid[start][end]=1\n",
    "        #                     break\n",
    "        for a,b in queries:\n",
    "            if a==b:\n",
    "                res.append(False)\n",
    "            elif grid[a][b]==1:\n",
    "                res.append(True)\n",
    "            else:\n",
    "                res.append(False)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:\n",
    "         # 构建邻接表\n",
    "        adj = [[] for _ in range(numCourses)]\n",
    "        for cur, pre in prerequisites:\n",
    "            adj[pre].append(cur)\n",
    "\n",
    "        # 来判断先决条件关系,判断u是否是v的先决条件\n",
    "        def isPrerequisite(u, v):\n",
    "            # 从u开始深度优先搜索，看看能否到达v\n",
    "            visited = set()\n",
    "            # 模拟栈，存放当前节点的邻接节点\n",
    "            stack = [v]\n",
    "            while stack:\n",
    "                current = stack.pop()\n",
    "                visited.add(current)\n",
    "                if current == u:\n",
    "                    return True\n",
    "                for neighbor in adj[current]:\n",
    "                    if neighbor not in visited:\n",
    "                        stack.append(neighbor)\n",
    "            return False\n",
    "\n",
    "        # 对每个查询进行判断\n",
    "        answer = []\n",
    "        for u, v in queries:\n",
    "            answer.append(isPrerequisite(u, v))\n",
    "        return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:\n",
    "        # 求拓扑排序的问题，感觉是 入度表+BFS 的方式更好理解一些\n",
    "        indegrees = [0] * numCourses    # 入度\n",
    "        # 建图\n",
    "        edges = collections.defaultdict(list)\n",
    "        for p in prerequisites:\n",
    "            indegrees[p[0]] += 1\n",
    "            edges[p[1]].append(p[0])\n",
    "        # print(indegrees)\n",
    "        # print(edges)\n",
    "\n",
    "        # 队列初始化，入度为0的节点进入队列\n",
    "        queue = collections.deque()\n",
    "        for i, indegree in enumerate(indegrees):\n",
    "            if indegree == 0:\n",
    "                queue.append(i)\n",
    "        # print(queue)\n",
    "\n",
    "        # 初始化祖先表\n",
    "        father = [set() for _ in range(numCourses)]\n",
    "\n",
    "        res = []\n",
    "\n",
    "        visited = 0     # 看是否能拓扑排序完\n",
    "        while queue:\n",
    "            cur = queue.popleft()\n",
    "            visited += 1\n",
    "            res.append(cur)\n",
    "            # 遍历下一层节点\n",
    "            for nxt in edges[cur]:\n",
    "                father[nxt].add(cur)\n",
    "                father[nxt].update(father[cur])\n",
    "                indegrees[nxt] -=1\n",
    "                if indegrees[nxt] == 0:\n",
    "                    queue.append(nxt)\n",
    "        print(res)\n",
    "        print(father)\n",
    "\n",
    "        # 根据祖先表判断课程先修情况\n",
    "        ans = [False]*len(queries)\n",
    "        for i, (u, v) in enumerate(queries):\n",
    "            if v in father[u]:\n",
    "                ans[i] = True\n",
    "        \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:\n",
    "        graph = defaultdict(list)\n",
    "        for x, y in prerequisites:\n",
    "            graph[x].append(y)\n",
    "\n",
    "        def bfs(start, end) -> bool:\n",
    "            q = deque([start])\n",
    "            vis = set([start])\n",
    "            while q:\n",
    "                if end in vis:\n",
    "                    return True\n",
    "                node = q.popleft()\n",
    "                for vertex in graph[node]:\n",
    "                    if vertex not in vis:\n",
    "                        vis.add(vertex)\n",
    "                        q.append(vertex)\n",
    "            return False\n",
    "\n",
    "        for i in range(len(queries)):\n",
    "            u, j = queries[i]\n",
    "            queries[i] = bfs(u, j)\n",
    "        return queries"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:\n",
    "        dct, i = collections.defaultdict(set), min(numCourses, len(prerequisites))\n",
    "        while i != 0:\n",
    "            for x, y in prerequisites:\n",
    "                dct[y] |= ({x} | dct[x])\n",
    "            i -= 1\n",
    "        for j in range(len(queries)):\n",
    "            if dct[queries[j][1]] == set() or queries[j][0] not in dct[queries[j][1]]: queries[j] = False\n",
    "            else: queries[j] = True\n",
    "        return queries"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:\n",
    "        dct, i = collections.defaultdict(set), min(numCourses, len(prerequisites))\n",
    "        while i != 0:\n",
    "            for x, y in prerequisites:\n",
    "                dct[y] |= ({x} | dct[x])\n",
    "            i -= 1\n",
    "        for j in range(len(queries)):\n",
    "            if dct[queries[j][1]] == set() or queries[j][0] not in dct[queries[j][1]]: queries[j] = False\n",
    "            else: queries[j] = True\n",
    "        return queries"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:\n",
    "        map = [set() for _ in range(numCourses)]\n",
    "        for rely, contribute in prerequisites:\n",
    "            map[contribute].add(rely)\n",
    "        ans = []\n",
    "        def judge(querie):\n",
    "            rely, contribute = querie\n",
    "            searching = [contribute]\n",
    "            searched = set()\n",
    "            while searching:\n",
    "                if rely in searching:\n",
    "                    return True\n",
    "                index = searching.pop(0)\n",
    "                searched.add(index)\n",
    "                news = map[index]\n",
    "                searching = list(news | set(searching) - searched)\n",
    "            return False\n",
    "        for querie in queries:\n",
    "            ans.append(judge(querie))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:\n",
    "        tempdict=defaultdict(set)\n",
    "        for d in prerequisites:\n",
    "            tempdict[d[0]].add(d[1])\n",
    "\n",
    "        def searchq(pre,aft):\n",
    "            templist={pre}\n",
    "            while templist:\n",
    "                childlist=set()\n",
    "                for p in templist:\n",
    "                    for a in tempdict[p]:\n",
    "                        if a==aft:\n",
    "                            return True\n",
    "                        childlist.add(a)\n",
    "                templist=childlist-templist\n",
    "            return False\n",
    "        return [searchq(x,y) for x,y in queries ]\n",
    "                    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:\n",
    "        map = [set() for _ in range(numCourses)]\n",
    "        for rely, contribute in prerequisites:\n",
    "            map[contribute].add(rely)\n",
    "        ans = []\n",
    "        def judge(querie):\n",
    "            rely, contribute = querie\n",
    "            searching = [contribute]\n",
    "            searched = set()\n",
    "            while searching:\n",
    "                if rely in searching:\n",
    "                    return True\n",
    "                index = searching.pop(-1)\n",
    "                searched.add(index)\n",
    "                news = map[index]\n",
    "                searching = list(news | set(searching) - searched)\n",
    "            return False\n",
    "        for querie in queries:\n",
    "            ans.append(judge(querie))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:\n",
    "        edges = [[] for _ in range(numCourses)]\n",
    "        ispre = [[False]*numCourses for _ in range(numCourses)]\n",
    "        inde = [0]*numCourses\n",
    "        for i,j in prerequisites:\n",
    "            edges[i].append(j)\n",
    "            inde[j] += 1\n",
    "\n",
    "        child_list = [[] for _ in range(numCourses)]\n",
    "\n",
    "        q = [index for index in range(numCourses) if inde[index]==0]\n",
    "        while q:\n",
    "            node = q.pop(0)\n",
    "            for child in edges[node]:\n",
    "                ispre[node][child] = True\n",
    "                for j in range(numCourses):\n",
    "                    ispre[j][child] = ispre[j][child] or ispre[j][node]\n",
    "                inde[child] -=1\n",
    "                if inde[child] == 0:\n",
    "                    q.append(child)\n",
    "        res = []\n",
    "        for i,j in queries:\n",
    "           res.append(ispre[i][j])\n",
    "        return res\n",
    "\n",
    "  \n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:\n",
    "        dic = defaultdict(list)\n",
    "        indgree = [0]*numCourses #入度\n",
    "\n",
    "        isPre = [[False]*numCourses for _ in range(numCourses)]\n",
    "        for u,v in prerequisites: \n",
    "            indgree[v] += 1\n",
    "            dic[u].append(v)\n",
    "        \n",
    "        queue = collections.deque()\n",
    "        for i in range(numCourses):\n",
    "            if indgree[i] == 0:\n",
    "                queue.append(i)\n",
    "\n",
    "        while queue:\n",
    "            cur = queue.popleft()\n",
    "            for nxt in dic[cur]:\n",
    "                isPre[cur][nxt] = True\n",
    "\n",
    "                #更新所有相关的组合\n",
    "                for node in range(numCourses):\n",
    "                    isPre[node][nxt] = isPre[node][nxt] or isPre[node][cur]\n",
    "                \n",
    "                indgree[nxt] -= 1\n",
    "                if indgree[nxt] == 0 :\n",
    "                    queue.append(nxt)\n",
    "        res = []\n",
    "        for i,j in queries:\n",
    "            res.append(isPre[i][j])\n",
    "        return res \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:\n",
    "        f = [[False] * numCourses for _ in range(numCourses)]\n",
    "        for x, y in prerequisites:\n",
    "            f[x][y] = True\n",
    "        for k in range(numCourses):\n",
    "            for i in range(numCourses):\n",
    "                for j in range(numCourses):\n",
    "                    if f[i][k] and f[k][j]:\n",
    "                        f[i][j] = True\n",
    "        return [f[a][b] for a,b in queries]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:\n",
    "        if len(prerequisites) == 0:\n",
    "            return [False]*numCourses\n",
    "        graph = [[False for _ in range(numCourses)] for _ in range(numCourses)]\n",
    "            \n",
    "        for pre, post in prerequisites:\n",
    "            graph[pre][post] = True\n",
    "        \n",
    "\n",
    "        def help(pre, post):\n",
    "            graph[pre][post] = True\n",
    "            for root in graph[:][pre]:\n",
    "                if graph[root][pre] and root != pre:\n",
    "                    help(root, post)\n",
    "        \n",
    "        for k in range(numCourses):\n",
    "            for i in range(numCourses):\n",
    "                for j in range(numCourses):\n",
    "                    if graph[i][k] and graph[k][j]:\n",
    "                        graph[i][j] = True\n",
    "        # print(graph)\n",
    "        \n",
    "        res = []\n",
    "        for p, q in queries:\n",
    "            res.append(graph[p][q])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkIfPrerequisite(self, n: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:\n",
    "        g = [[] for _ in range(n)]\n",
    "\n",
    "        f = [[float('inf')] * n for _ in range(n)]\n",
    "\n",
    "        for a, b in prerequisites:\n",
    "            f[a][b] = 1\n",
    "\n",
    "        for k in range(n):\n",
    "            for i in range(n):\n",
    "                for j in range(n):\n",
    "                    f[i][j] = min(f[i][j], f[i][k] + f[k][j])\n",
    "        res = []\n",
    "        for a, b in queries:\n",
    "            if f[a][b] != float('inf'):\n",
    "                res.append(True)\n",
    "            else:\n",
    "                res.append(False)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkIfPrerequisite(self, n: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:\n",
    "        g = [[] for _ in range(n)]\n",
    "        vis = [False] * n\n",
    "        isConn = [[False] * n for _ in range(n)]\n",
    "        for a, b in prerequisites:\n",
    "            g[a].append(b)\n",
    "\n",
    "        def dfs(node):\n",
    "            if vis[node]:\n",
    "                return \n",
    "            vis[node] = True\n",
    "            for ch in g[node]:\n",
    "                dfs(ch)\n",
    "                isConn[node][ch] = True\n",
    "                for i in range(n):\n",
    "                    isConn[node][i] = isConn[node][i] | isConn[ch][i]\n",
    "        \n",
    "        for i in range(n):\n",
    "            dfs(i)\n",
    "        \n",
    "        res = []\n",
    "\n",
    "        for a, b in queries:\n",
    "            res.append(isConn[a][b])\n",
    "        return res\n",
    "\n",
    "\n",
    "        # f = [[float('inf')] * n for _ in range(n)]\n",
    "\n",
    "        # for a, b in prerequisites:\n",
    "        #     f[a][b] = 1\n",
    "\n",
    "        # for k in range(n):\n",
    "        #     for i in range(n):\n",
    "        #         for j in range(n):\n",
    "        #             f[i][j] = min(f[i][j], f[i][k] + f[k][j])\n",
    "        # res = []\n",
    "        # for a, b in queries:\n",
    "        #     if f[a][b] != float('inf'):\n",
    "        #         res.append(True)\n",
    "        #     else:\n",
    "        #         res.append(False)\n",
    "        # return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkIfPrerequisite(self, n: int, p: List[List[int]], q: List[List[int]]) -> List[bool]:\n",
    "        ans = [[False]*n for _ in range(n)]\n",
    "        for a,b in p:\n",
    "            ans[a][b] = True\n",
    "\n",
    "        for k in range(n):\n",
    "            for i in range(n):\n",
    "                for j in range(n):\n",
    "                    if not ans[i][j]:\n",
    "                        ans[i][j] = ans[i][k] and ans[k][j]\n",
    "        return [ans[a][b] for a,b in q]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:\n",
    "        inf = 10**9\n",
    "        dp = [[inf if i!=j else 0 for j in range(numCourses)] for i in range(numCourses)]\n",
    "        for x,y in prerequisites:\n",
    "            dp[x][y] = 0\n",
    "        for k in range(numCourses):\n",
    "            for i in range(numCourses):\n",
    "                for j in range(numCourses):\n",
    "                    dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])\n",
    "        ans = []\n",
    "        for l,r in queries:\n",
    "            ans.append(dp[l][r]==0)\n",
    "        return ans\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:\n",
    "        parents=defaultdict(list)\n",
    "        for u,v in prerequisites:\n",
    "            parents[v].append(u)\n",
    "        ans=[]\n",
    "        for u,v in queries:\n",
    "            visited=[False]*numCourses\n",
    "            q=deque([v])\n",
    "            while q:\n",
    "                nv=q.popleft()\n",
    "                if visited[nv]:\n",
    "                    continue\n",
    "                visited[nv]=True\n",
    "                if nv==u:\n",
    "                    break\n",
    "                for nu in parents[nv]:\n",
    "                    q.append(nu)\n",
    "            ans.append(visited[u])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:\n",
    "\n",
    "        indegree = defaultdict(int)\n",
    "        relation = defaultdict(list)\n",
    "        for x, y in prerequisites:\n",
    "            indegree[y] += 1\n",
    "            relation[x].append(y)\n",
    "        q = [x for x in range(numCourses) if x not in indegree]\n",
    "        res = defaultdict(set)\n",
    "        while q:\n",
    "            v = q.pop(0)\n",
    "            for i in relation.get(v, []):\n",
    "                res[i].add(v)\n",
    "                res[i].update(res[v])\n",
    "                indegree[i] -= 1\n",
    "                if indegree[i] == 0:\n",
    "                    q.append(i)\n",
    "        print(\"res:\", res)\n",
    "\n",
    "        o  = []\n",
    "        for x, y in queries:\n",
    "            if x in res[y]:\n",
    "                o.append(True)\n",
    "            else:\n",
    "                o.append(False)\n",
    "\n",
    "        return o"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:\n",
    "        dic = defaultdict(list)\n",
    "        indgree = [0]*numCourses #入度\n",
    "\n",
    "        isPre = [[False]*numCourses for _ in range(numCourses)]\n",
    "\n",
    "        for u,v in prerequisites: \n",
    "            indgree[v] += 1\n",
    "            dic[u].append(v)\n",
    "        \n",
    "        queue = collections.deque()\n",
    "        for i in range(numCourses):\n",
    "            if indgree[i] == 0:\n",
    "                queue.append(i)\n",
    "\n",
    "        while queue:\n",
    "            cur = queue.popleft()\n",
    "            for nxt in dic[cur]:\n",
    "                isPre[cur][nxt] = True\n",
    "\n",
    "                #更新所有相关的组合\n",
    "                # node 能到cur,就能到nxt\n",
    "                for node in range(numCourses):\n",
    "                    isPre[node][nxt] = isPre[node][nxt] or isPre[node][cur]\n",
    "                \n",
    "                indgree[nxt] -= 1\n",
    "                if indgree[nxt] == 0 :\n",
    "                    queue.append(nxt)\n",
    "        res = []\n",
    "        for i,j in queries:\n",
    "            res.append(isPre[i][j])\n",
    "        return res \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:\n",
    "        parents=defaultdict(list)\n",
    "        for u,v in prerequisites:\n",
    "            parents[v].append(u)\n",
    "        ans=[]\n",
    "\n",
    "        for u,v in queries:\n",
    "            visited=[False]*numCourses\n",
    "            q=deque([v])\n",
    "            while q:\n",
    "                nv=q.popleft()\n",
    "                if visited[nv]:\n",
    "                    continue\n",
    "                visited[nv]=True\n",
    "                if nv==u:\n",
    "                    break\n",
    "                for nu in parents[nv]:\n",
    "                    q.append(nu)\n",
    "            ans.append(visited[u])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:\n",
    "\n",
    "        indegree = defaultdict(int)\n",
    "        relation = defaultdict(list)\n",
    "        for x, y in prerequisites:\n",
    "            indegree[y] += 1\n",
    "            relation[x].append(y)\n",
    "        q = [x for x in range(numCourses) if x not in indegree]\n",
    "        res = defaultdict(set)\n",
    "        while q:\n",
    "            v = q.pop(0)\n",
    "            for i in relation.get(v, []):\n",
    "                if v not in res[i]:\n",
    "                    res[i].add(v)\n",
    "                    res[i].update(res[v])\n",
    "                indegree[i] -= 1\n",
    "                if indegree[i] == 0:\n",
    "                    q.append(i)\n",
    "        print(\"res:\", res)\n",
    "\n",
    "        o  = []\n",
    "        for x, y in queries:\n",
    "            if x in res[y]:\n",
    "                o.append(True)\n",
    "            else:\n",
    "                o.append(False)\n",
    "\n",
    "        return o\n",
    "\n",
    "        return o"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkIfPrerequisite(self, n: int, p: List[List[int]], q: List[List[int]]) -> List[bool]:\n",
    "\n",
    "        g = defaultdict(list)\n",
    "        deg = [0]*n\n",
    "        isPre = [[False]*n for _ in range(n)]\n",
    "        for a,b in p:\n",
    "            g[a].append(b)\n",
    "            deg[b] += 1\n",
    "        cur = [i for i in range(n) if deg[i] == 0]\n",
    "        while cur:\n",
    "            nxt = []\n",
    "            for x in cur:\n",
    "                for y in g[x]:\n",
    "                    isPre[x][y] = True\n",
    "                    deg[y] -= 1\n",
    "                    for i in range(n):\n",
    "                        isPre[i][y] = isPre[i][y] or isPre[i][x]\n",
    "                    if deg[y] == 0:\n",
    "                        nxt.append(y)\n",
    "            cur = nxt\n",
    "        ans = []\n",
    "        for a,b in q:\n",
    "            ans.append(isPre[a][b])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:\n",
    "        import queue\n",
    "        q = queue.Queue()\n",
    "        indegree = [0]*numCourses\n",
    "        vis = [False]*numCourses\n",
    "        prevs = [set() for _ in range(numCourses)]\n",
    "        nexts = [[] for _ in range(numCourses)]\n",
    "        for u,v in prerequisites:\n",
    "            indegree[v] += 1\n",
    "            nexts[u].append(v)\n",
    "        for i,d in enumerate(indegree):\n",
    "            if d == 0:\n",
    "                q.put(i)\n",
    "                vis[i] = True\n",
    "        while not q.empty():\n",
    "            u = q.get()\n",
    "            for v in nexts[u]:\n",
    "                indegree[v] -= 1\n",
    "                prevs[v].add(u)\n",
    "                prevs[v] = prevs[v].union(prevs[u])\n",
    "                if indegree[v] == 0:\n",
    "                    if not vis[v]:\n",
    "                        q.put(v)\n",
    "                    vis[v] = True\n",
    "        res = []\n",
    "        #print(prevs)\n",
    "        for x,y in queries:\n",
    "            if x in prevs[y]:\n",
    "                res.append(True)\n",
    "            else:\n",
    "                res.append(False)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def checkIfPrerequisite(\n",
    "        self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]\n",
    "    ) -> List[bool]:\n",
    "        def dfs(x, y):\n",
    "            if x == y:\n",
    "                return True\n",
    "\n",
    "            if x in memo and y in memo[x]:\n",
    "                return memo[x][y]\n",
    "\n",
    "            for nxt in adjs[x]:\n",
    "                if dfs(nxt, y):\n",
    "                    memo[x][y] = True\n",
    "\n",
    "                    return True\n",
    "\n",
    "            memo[x][y] = False\n",
    "            return False\n",
    "\n",
    "        adjs = collections.defaultdict(list)\n",
    "        for x, y in prerequisites:\n",
    "            adjs[x].append(y)\n",
    "\n",
    "        memo = collections.defaultdict(dict)\n",
    "        res = []\n",
    "        for x, y in queries:\n",
    "            res.append(dfs(x, y))\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:\n",
    "        nextNodes = defaultdict(set)\n",
    "        \n",
    "        for u, v in prerequisites:\n",
    "            nextNodes[u].add(v)\n",
    "        \n",
    "        ans = set()\n",
    "        for i in range(numCourses):\n",
    "            d = deque([i])\n",
    "            asked = {i}\n",
    "\n",
    "            while d:\n",
    "                u = d.popleft()\n",
    "                for v in nextNodes[u]:\n",
    "                    if v not in asked:\n",
    "                        asked.add(v)\n",
    "                        d.append(v)\n",
    "                        ans.add((i, v))\n",
    "        \n",
    "        return [(u, v) in ans for u, v in queries]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:\n",
    "        target = {query[1]: [] for query in queries}\n",
    "        for index, query in enumerate(queries):\n",
    "            target[query[1]].append((query[0], query[1], index))\n",
    "        result = [False] * len(queries)\n",
    "\n",
    "        degree = [0] * numCourses\n",
    "        nexts = [set() for i in range(numCourses)]\n",
    "        # pres = [set() for i in range(numCourses)]\n",
    "        pres = [0]*numCourses\n",
    "        for pre, next in prerequisites:\n",
    "            degree[next] += 1\n",
    "            nexts[pre].add(next)\n",
    "            pres[next] += 1 << pre\n",
    "\n",
    "        q = deque([i for i in range(numCourses) if degree[i] == 0])\n",
    "        while q:\n",
    "            course = q.popleft()\n",
    "            for next in nexts[course]:\n",
    "                degree[next] -= 1\n",
    "                pres[next] = pres[next] | pres[course]\n",
    "                if degree[next] == 0:\n",
    "                    # for _pre in list(pres[next]):\n",
    "                        # pres[next] |= pres[_pre]\n",
    "                    q.append(next)\n",
    "                    for query in target.get(next, []):\n",
    "                        result[query[2]] = ((1 << query[0]) & pres[next]) > 0\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:\n",
    "        g = defaultdict(set)\n",
    "        for x, y in prerequisites:\n",
    "            g[x].add(y)\n",
    "\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            return reduce(or_, map(dfs, g[i]), g[i])\n",
    "\n",
    "        for i in range(numCourses):\n",
    "            g[i] = dfs(i)\n",
    "        return [y in g[x] for x, y in queries]\n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:\n",
    "        g = defaultdict(set)\n",
    "        for x, y in prerequisites:\n",
    "            g[x].add(y)\n",
    "        @cache\n",
    "        def dfs(u):\n",
    "            return reduce(or_, map(dfs, g[u]), g[u])\n",
    "\n",
    "        for i in range(numCourses):\n",
    "            g[i] = dfs(i)\n",
    "        return [y in g[x] for x, y in queries]\n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:\n",
    "        \"\"\"dfs：把子节点的子节点全部加到当前节点的子节点集合中\"\"\"\n",
    "        g = defaultdict(set)\n",
    "        for x, y in prerequisites:\n",
    "            g[x].add(y)\n",
    "        @cache\n",
    "        def dfs(u):\n",
    "            son = set()\n",
    "            for nxt in g[u]:\n",
    "                son.add(nxt)\n",
    "                son |= dfs(nxt)\n",
    "            return son\n",
    "        for i in range(numCourses):\n",
    "            g[i] |= dfs(i)\n",
    "        return [y in g[x] for x, y in queries]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:\n",
    "        g = defaultdict(set)\n",
    "        for x, y in prerequisites:\n",
    "            g[x].add(y)\n",
    "        @cache\n",
    "        def dfs(u):\n",
    "            son = set()\n",
    "            for nxt in g[u]:\n",
    "                son.add(nxt)\n",
    "                son |= dfs(nxt)\n",
    "            return son\n",
    "        for i in range(numCourses):\n",
    "            g[i] |= dfs(i)\n",
    "        return [y in g[x] for x, y in queries]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:\n",
    "        g = defaultdict(set)\n",
    "        for x, y in prerequisites:\n",
    "            g[x].add(y)\n",
    "        @cache\n",
    "        def dfs(u):\n",
    "            son = set()\n",
    "            for nxt in g[u]:\n",
    "                son.add(nxt)\n",
    "                son |= dfs(nxt)\n",
    "            return son\n",
    "        for i in range(numCourses):\n",
    "            g[i] |= dfs(i)\n",
    "        return [y in g[x] for x, y in queries]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkIfPrerequisite(self, n: int, p: List[List[int]], q: List[List[int]]) -> List[bool]:\n",
    "        g = defaultdict(set)\n",
    "        d = defaultdict(int)\n",
    "        for x, y in p:\n",
    "            d[y] += 1 \n",
    "            g[x].add(y)\n",
    "        a = defaultdict(int)\n",
    "        s = [j for j in range(n) if d[j]==0]\n",
    "        while s:\n",
    "            tmp = []\n",
    "            for j in s:\n",
    "                for k in g[j]:\n",
    "                    a[(j, k)] = 1 \n",
    "                    for i in range(n):\n",
    "                        if a[(i, j)]:\n",
    "                            a[(i, k)] = 1 \n",
    "                    d[k] -= 1 \n",
    "                    if d[k]==0:\n",
    "                        tmp.append(k)\n",
    "            s = tmp \n",
    "        return [bool(a[(i, j)]) for i, j in q]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkIfPrerequisite(\n",
    "        self, n: int, prerequisites: List[List[int]], queries: List[List[int]]\n",
    "    ) -> List[bool]:\n",
    "        f = [[False] * n for _ in range(n)]\n",
    "        for a, b in prerequisites:\n",
    "            f[a][b] = True\n",
    "        for k in range(n):\n",
    "            for i in range(n):\n",
    "                for j in range(n):\n",
    "                    if f[i][k] and f[k][j]:\n",
    "                        f[i][j] = True\n",
    "        return [f[a][b] for a, b in queries]\n",
    "\n",
    "class Solution:\n",
    "    def checkIfPrerequisite(\n",
    "        self, n: int, prerequisites: List[List[int]], queries: List[List[int]]\n",
    "    ) -> List[bool]:\n",
    "        f = [[False] * n for _ in range(n)]\n",
    "        g = [[] for _ in range(n)]\n",
    "        indeg = [0] * n\n",
    "        for a, b in prerequisites:\n",
    "            g[a].append(b)\n",
    "            indeg[b] += 1\n",
    "        q = deque(i for i, x in enumerate(indeg) if x == 0)\n",
    "        while q:\n",
    "            i = q.popleft()\n",
    "            for j in g[i]:\n",
    "                f[i][j] = True\n",
    "                for h in range(n):\n",
    "                    f[h][j] = f[h][j] or f[h][i]\n",
    "                indeg[j] -= 1\n",
    "                if indeg[j] == 0:\n",
    "                    q.append(j)\n",
    "        return [f[a][b] for a, b in queries]\n",
    "\n",
    "class Solution:\n",
    "    def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:\n",
    "        g = [[] for _ in range(numCourses)]\n",
    "        indgree = [0] * numCourses\n",
    "        isPre = [[False] * numCourses for _ in range(numCourses)]\n",
    "        for p in prerequisites:\n",
    "            indgree[p[1]] += 1\n",
    "            g[p[0]].append(p[1])\n",
    "\n",
    "        q = []\n",
    "        for i in range(numCourses):\n",
    "            if indgree[i] == 0:\n",
    "                q.append(i)\n",
    "        while len(q) > 0:\n",
    "            cur = q[0]\n",
    "            q.pop(0)\n",
    "            for ne in g[cur]:\n",
    "                isPre[cur][ne] = True\n",
    "                for i in range(numCourses):\n",
    "                    isPre[i][ne] = isPre[i][ne] or isPre[i][cur]\n",
    "                indgree[ne] -= 1\n",
    "                if indgree[ne] == 0:\n",
    "                    q.append(ne)\n",
    "        res = []\n",
    "        for query in queries:\n",
    "            res.append(isPre[query[0]][query[1]])\n",
    "        return res\n",
    "\n",
    "class Solution:\n",
    "    def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:\n",
    "        g = [[] for _ in range(numCourses)]\n",
    "        vi = [False] * numCourses\n",
    "        isPre = [[False] * numCourses for _ in range(numCourses)]\n",
    "        for p in prerequisites:\n",
    "            g[p[0]].append(p[1])\n",
    "\n",
    "        def dfs(cur):\n",
    "            if vi[cur]:\n",
    "                return\n",
    "            vi[cur] = True\n",
    "            for ne in g[cur]:\n",
    "                dfs(ne)\n",
    "                isPre[cur][ne] = True\n",
    "                for i in range(numCourses):\n",
    "                    isPre[cur][i] = isPre[cur][i] | isPre[ne][i]\n",
    "\n",
    "        for i in range(numCourses):\n",
    "            dfs(i)\n",
    "        res = []\n",
    "        for query in queries:\n",
    "            res.append(isPre[query[0]][query[1]])\n",
    "        return res\n",
    "        \n",
    "\n",
    "class Solution:\n",
    "    def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:\n",
    "        d, d_ = defaultdict(set), {}\n",
    "        for a, b in prerequisites: d[a].add(b)\n",
    "        while d != d_:\n",
    "            d_ = deepcopy(d)\n",
    "            for a, se in d.items():\n",
    "                for b in set(se): \n",
    "                    if b in d: se |= d[b]\n",
    "        return [v in d[u] for u, v in queries]        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:\n",
    "        target = {query[1]: [] for query in queries}\n",
    "        for index, query in enumerate(queries):\n",
    "            target[query[1]].append((query[0], query[1], index))\n",
    "        result = [False] * len(queries)\n",
    "\n",
    "        degree = [0] * numCourses\n",
    "        nexts = [set() for i in range(numCourses)]\n",
    "        pres = [set() for i in range(numCourses)]\n",
    "        for pre, next in prerequisites:\n",
    "            degree[next] += 1\n",
    "            nexts[pre].add(next)\n",
    "            pres[next].add(pre)\n",
    "\n",
    "        q = deque([i for i in range(numCourses) if degree[i] == 0])\n",
    "        while q:\n",
    "            course = q.popleft()\n",
    "            for next in nexts[course]:\n",
    "                degree[next] -= 1\n",
    "\n",
    "                if degree[next] == 0:\n",
    "                    for _pre in list(pres[next]):\n",
    "                        pres[next] |= pres[_pre]\n",
    "                    q.append(next)\n",
    "                    for query in target.get(next, []):\n",
    "                        result[query[2]] = query[0] in pres[next]\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "class Solution:\n",
    "    def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:\n",
    "        # 首先构造先决条件表\n",
    "        nei_in=[set() for _ in range(numCourses)]\n",
    "        nei_out=[set() for _ in range(numCourses)]\n",
    "        nei_pre=[set() for _ in range(numCourses)]\n",
    "\n",
    "        for prerequisite in prerequisites:\n",
    "            nei_out[prerequisite[0]].add(prerequisite[1])\n",
    "            nei_in[prerequisite[1]].add(prerequisite[0])\n",
    "        queue=deque([i for i in range(numCourses) if len(nei_in[i])==0])\n",
    "\n",
    "        while queue:\n",
    "            course=queue.popleft()\n",
    "            for nei in nei_out[course]:\n",
    "                nei_in[nei].remove(course)\n",
    "                nei_pre[nei].add(course)\n",
    "                nei_pre[nei]=nei_pre[nei].union(nei_pre[course])\n",
    "                if len(nei_in[nei])==0:\n",
    "                    queue.append(nei)\n",
    "        \n",
    "        return [(query[0] in nei_pre[query[1]]) for query in queries]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:\n",
    "        a = {}\n",
    "\n",
    "        for i,j in prerequisites:\n",
    "            a[j] = a.get(j,[]) + [i]\n",
    "\n",
    "        @cache\n",
    "        def get(n):\n",
    "            ans = set()\n",
    "            for i in a.get(n,[]) :\n",
    "                ans |= get(i) | {i}\n",
    "            return ans |{n}\n",
    "\n",
    "        for i in a :\n",
    "            t = set()\n",
    "            for j in a[i]:\n",
    "                t |= get(j)\n",
    "            a[i] = t\n",
    "\n",
    "        ans = []\n",
    "        for i,j in queries:\n",
    "            if i in a.get(j,[]):\n",
    "                ans.append(True)\n",
    "            else:\n",
    "                ans.append(False)\n",
    "        return ans \n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:\n",
    "        children = defaultdict(set)\n",
    "        numChildren = defaultdict(int)\n",
    "        revG = defaultdict(list)\n",
    "        lookup = defaultdict(list)\n",
    "\n",
    "        for prere in prerequisites:\n",
    "            revG[prere[0]].append(prere[1])\n",
    "            numChildren[prere[1]] += 1\n",
    "        \n",
    "        for i, q in enumerate(queries):\n",
    "            lookup[q[1]].append((q[0], i))\n",
    "        \n",
    "        q = deque([i for i in range(numCourses) if numChildren[i] == 0])\n",
    "        ans = [False] * len(queries)\n",
    "\n",
    "        while q:\n",
    "            c = q.popleft()\n",
    "            for qprere, qi in lookup[c]:\n",
    "                ans[qi] = qprere in children[c]\n",
    "            for parent in revG[c]:\n",
    "                children[parent].add(c)\n",
    "                children[parent] = children[parent].union(children[c])\n",
    "                numChildren[parent] -= 1\n",
    "                if numChildren[parent] == 0:\n",
    "                    q.append(parent)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkIfPrerequisite(self, numCourses, prerequisites, queries):\n",
    "\n",
    "        classMap = self.buildMap(numCourses, prerequisites)\n",
    "        ans = []\n",
    "        record = {}\n",
    "        for query in queries:\n",
    "            ans.append(self.dfs(classMap, record, query))\n",
    "        print(record)\n",
    "\n",
    "        return ans\n",
    "\n",
    "    def dfs(self, classMap, record, query):\n",
    "        last = query[0]\n",
    "        first = query[1]\n",
    "        if record.get((first, last), -1) == 1 or classMap[first][last]==1:\n",
    "            record[(first, last)] = 1\n",
    "            return True\n",
    "        if record.get((first, last), -1) == 0:\n",
    "            return False\n",
    "\n",
    "        for i in range(len(classMap[first])):\n",
    "            if classMap[first][i] == 1:\n",
    "                record[(first, i)] = 1\n",
    "                if (first, last) in record:\n",
    "                    record[(first, last)] = 1\n",
    "                    return True\n",
    "                ans = self.dfs(classMap, record, [last, i])\n",
    "                if ans:\n",
    "                    record[(i, last)] = 1\n",
    "                    return ans\n",
    "                else:\n",
    "                    record[(i, last)] = 0\n",
    "        record[(first, last)] = 0\n",
    "        return False\n",
    "\n",
    "    def buildMap(self, numCourses, prerequisites):\n",
    "        classMap = [[0] * numCourses for _ in range(numCourses)]\n",
    "\n",
    "        for i in range(len(prerequisites)):\n",
    "            prerequisite = prerequisites[i]\n",
    "            pre = prerequisite[0]\n",
    "            cur = prerequisite[1]\n",
    "\n",
    "            classMap[cur][pre] = 1\n",
    "\n",
    "        return classMap"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "class Solution:\n",
    "    def checkIfPrerequisite(self, n: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(a,b):\n",
    "            if a==b:\n",
    "                return True\n",
    "            if not graph[a]:\n",
    "                return False\n",
    "            for i in graph[a]:\n",
    "                if dfs(i,b):\n",
    "                    return True\n",
    "            return False\n",
    "            \n",
    "        graph=defaultdict(list)\n",
    "        for a,b in prerequisites:\n",
    "            graph[b].append(a)\n",
    "        ans = []\n",
    "        for a, b in queries:\n",
    "            ans.append(dfs(b,a))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from graphlib import TopologicalSorter\r\n",
    "pa: list[set[int]] = [set() for _ in range(100)]\r\n",
    "q: list[dict[int, list[int]]] = [dict() for _ in range(100)]\r\n",
    "children: list[list[int]] = [list() for _ in range(100)]\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:\r\n",
    "        res = [False] * len(queries)\r\n",
    "        for i in range(numCourses):\r\n",
    "            pa[i].clear()\r\n",
    "            q[i].clear()\r\n",
    "            children[i].clear()\r\n",
    "        \r\n",
    "        for i, (u, v) in enumerate(queries):\r\n",
    "            q[v].setdefault(u, list())\r\n",
    "            q[v][u].append(i)\r\n",
    "\r\n",
    "        ts = TopologicalSorter()\r\n",
    "        for u, v in prerequisites:\r\n",
    "            ts.add(v, u)\r\n",
    "            children[u].append(v)\r\n",
    "\r\n",
    "        ts.prepare()\r\n",
    "        while ts.is_active():\r\n",
    "            for u in ts.get_ready():\r\n",
    "                for v, idx in q[u].items():\r\n",
    "                    for i in idx:\r\n",
    "                        res[i] = v in pa[u]\r\n",
    "                for v in children[u]:\r\n",
    "                    pa[v].update(pa[u])\r\n",
    "                    pa[v].add(u)\r\n",
    "                \r\n",
    "                ts.done(u)\r\n",
    "        \r\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:\n",
    "        d = defaultdict(set)\n",
    "        for pc, c in prerequisites: d[pc].add(c)\n",
    "        @cache\n",
    "        def check(pc, c):\n",
    "            if c in d[pc]:\n",
    "                return True \n",
    "            else:\n",
    "                return any(check(nc, c) for nc in d[pc])\n",
    "        \n",
    "        return [check(pc, c) for pc, c in queries]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:\n",
    "        self.map = defaultdict(list)\n",
    "        self.pre_map = defaultdict(list)\n",
    "        for pre in prerequisites:\n",
    "            self.map[pre[0]].append(pre[1])\n",
    "        for i in range(numCourses):\n",
    "            self.dfs(i, i)\n",
    "        res = [True if query[1] in self.pre_map[query[0]] else False for query in queries]\n",
    "        return res\n",
    "\n",
    "    @lru_cache\n",
    "    def dfs(self, start, course):\n",
    "        if not self.map[course]:\n",
    "            return\n",
    "        for c in self.map[course]:\n",
    "            self.pre_map[start].append(c)\n",
    "            self.dfs(start, c)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:\n",
    "        \"\"\"\n",
    "        Build single directed graph. For each query, check if there exists a path between the two nodes.\n",
    "        \"\"\"\n",
    "        graph = {i: set() for i in range(numCourses)}\n",
    "        for x, y in prerequisites:\n",
    "            graph[x].add(y)\n",
    "        cache = {}\n",
    "        def query(x, y):\n",
    "            if (x, y) not in cache:\n",
    "                ans = False\n",
    "                children = graph.get(x, set())\n",
    "                if y in children:\n",
    "                    ans = True\n",
    "                else:\n",
    "                    for z in children:\n",
    "                        if query(z, y):\n",
    "                            ans = True\n",
    "                            break\n",
    "                cache[(x,y)] = ans\n",
    "            return cache[(x, y)]\n",
    "        \n",
    "        ans = [query(x, y) for (x, y) in queries]\n",
    "        return ans\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[\n",
    "        bool]:\n",
    "        matrix = [[False] * numCourses for _ in range(numCourses)]\n",
    "        for a, b in prerequisites:\n",
    "            matrix[b][a] = True\n",
    "        ans = []\n",
    "\n",
    "        @cache\n",
    "        def check(pre, cou):\n",
    "            if matrix[cou][pre]:\n",
    "                return True\n",
    "            for i in range(numCourses):\n",
    "                if matrix[cou][i]:\n",
    "                    if check(pre, i):\n",
    "                        return True\n",
    "            return False\n",
    "\n",
    "        for u, v in queries:\n",
    "            ans.append(check(u, v))\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:\n",
    "        def search(u, v):\n",
    "            if u in pre[v]:\n",
    "                return True \n",
    "            if (u, v) in memo:\n",
    "                return memo[(u, v)]\n",
    "            for i in pre[v]:\n",
    "                temp = search(u, i)\n",
    "                if temp:\n",
    "                    memo[(u, v)] = True                    \n",
    "                    return True \n",
    "            memo[(u, v)] = False\n",
    "            return False \n",
    "        \n",
    "        pre = defaultdict(set)\n",
    "        for a, b in prerequisites:\n",
    "            pre[b].add(a)\n",
    "        res = []\n",
    "        memo = {}\n",
    "        for u, v in queries:\n",
    "            res.append(search(u, v))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkIfPrerequisite(self, n: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:\n",
    "        graph = {k: set() for k in range(n)}\n",
    "        if not prerequisites:\n",
    "            return [False for _ in range(len(queries))] #如果不存在先修课这个条件，返回False\n",
    "        for x in prerequisites:\n",
    "            graph[x[0]].add(x[1])#建图，存储后续课程，键为课程，值为对应课程的后续课程\n",
    "        ans = [] #存储答案\n",
    "        @functools.lru_cache(None) #缓存保存之前遍历到的ispre，避免计算重复\n",
    "        def ispre(lesson1,lesson2): #判断lesson1是不是lesson2的先修课程\n",
    "            if lesson1 == lesson2 or lesson2 in graph[lesson1]:\n",
    "                return True\n",
    "            #有一个满足则返回True\n",
    "            return any([ispre(lesson,lesson2) for lesson in graph[lesson1]])    \n",
    "        for x in queries:\n",
    "            ans.append(ispre(x[0],x[1]))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:\n",
    "        d = dict()\n",
    "        for x,y in prerequisites:\n",
    "            if x not in d:\n",
    "                d[x] = {y,}\n",
    "            else:\n",
    "                d[x].add(y)\n",
    "        cache = dict()\n",
    "        def dfs(x, target):\n",
    "            if (x, target) in cache:\n",
    "                return cache[(x, target)]\n",
    "            if x == target:\n",
    "                return True\n",
    "            if x not in d:\n",
    "                cache[(x,target)] = False\n",
    "                return False\n",
    "            for y in d[x]:\n",
    "                if dfs(y, target):\n",
    "                    cache[(x,target)] = True\n",
    "                    return True\n",
    "            cache[(x,target)] = False\n",
    "            return False\n",
    "        r = list()\n",
    "        for x, y in queries:\n",
    "            r.append(dfs(x,y))\n",
    "        return r\n",
    "\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:\n",
    "        dic=dict()\n",
    "        for i in range( numCourses):\n",
    "            dic[i]=set()\n",
    "        for i in  prerequisites:\n",
    "            s=dic.get(i[1],set())\n",
    "            s.add(i[0])\n",
    "            dic[i[1]]=s\n",
    "        memo=dict()\n",
    "        def find(father,son):\n",
    "            if (father,son) in memo:\n",
    "                return memo[(father,son)]\n",
    "            if father in dic[son]:\n",
    "                return True\n",
    "            else:\n",
    "                for i in dic[son]:\n",
    "                    if find(father,i)==True:\n",
    "                        memo[(father,son)]=True\n",
    "                        return True\n",
    "            memo[(father,son)]=False\n",
    "            return False\n",
    "        ans=[]\n",
    "        for i in queries:\n",
    "            ans.append(find(i[0],i[1]))\n",
    "        return ans\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:\n",
    "        adj = [set() for _ in range(numCourses)]\n",
    "        # 直接\n",
    "        for a, b in prerequisites:\n",
    "            adj[b].add(a)\n",
    "        \n",
    "        # 间接\n",
    "        encounter = set()\n",
    "        for i in range(numCourses):\n",
    "                \n",
    "            path = []\n",
    "            def dfs(i: int):\n",
    "                if i in encounter:\n",
    "                    path.append(i)\n",
    "                    path.extend(adj[i])\n",
    "                    return\n",
    "\n",
    "                path.append(i)\n",
    "                il = len(path)\n",
    "                for to in adj[i]:\n",
    "                    dfs(to)\n",
    "                \n",
    "                for p in path[il:]:\n",
    "                    adj[i].add(p)\n",
    "                    \n",
    "                encounter.add(i)\n",
    "\n",
    "\n",
    "            if i not in encounter:\n",
    "                dfs(i)\n",
    "        \n",
    "        return [u in adj[v] for u, v in queries]\n",
    "\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:\n",
    "        g = [[] for _ in range(numCourses)]\n",
    "        for a, b in prerequisites:\n",
    "            g[b].append(a)\n",
    "        m = len(queries)\n",
    "        @cache\n",
    "        def dfs(u, v):\n",
    "            if v in g[u]: return True\n",
    "            for x in g[u]:\n",
    "                if dfs(x, v):\n",
    "                    return True\n",
    "            return False\n",
    "        return [dfs(b, a) for a, b in queries]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:\n",
    "      course_list = [[] for _ in range(numCourses)]\n",
    "      for x, y in prerequisites:\n",
    "        course_list[y].append(x)\n",
    "\n",
    "      @cache\n",
    "      def check(u, v):\n",
    "        if course_list[v] == []:\n",
    "          return False\n",
    "        if u in course_list[v]:\n",
    "          return True\n",
    "        for vv in course_list[v]:\n",
    "          if check(u, vv):\n",
    "             return True\n",
    "        return False\n",
    "      \n",
    "      ans = []\n",
    "      for i, j in queries:\n",
    "        ans.append(check(i,j))\n",
    "      return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]: \n",
    "        # dfs(u,v) return u 是否 v 的前置\n",
    "        @cache\n",
    "        def dfs(u,v):\n",
    "            # print(\"dfs(%d,%d)\"%(u,v))\n",
    "            if v in d.keys():\n",
    "                if u in d[v]:\n",
    "                    return True\n",
    "                else:\n",
    "                    for i in d[v]:\n",
    "                        if dfs(u,i):\n",
    "                            return True\n",
    "                    return False\n",
    "            else:\n",
    "                return False\n",
    "\n",
    "        # d key:课程b   val:前置课程a\n",
    "        d={}\n",
    "        # a前置课程  b课程\n",
    "        for a,b in prerequisites:\n",
    "            if b in d.keys():\n",
    "                d[b].append(a)\n",
    "            else:\n",
    "                d[b]=[a]\n",
    "        print(\"d:\",d)\n",
    "\n",
    "        ans=[]\n",
    "        # u前置课程  v课程\n",
    "        for u,v in queries:\n",
    "            if v not in d.keys() or (u in d.keys() and v in d[u]):\n",
    "                # print(\"\\nif\")\n",
    "                ans.append(False)\n",
    "            else:\n",
    "                # print(\"\\nelse\")\n",
    "                ans.append(dfs(u,v))\n",
    "            \n",
    "            # print(\"u=%d,v=%d,ans=%s\"%(u,v,ans))\n",
    "        return ans\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:\n",
    "        d1 = defaultdict(set)\n",
    "        d2 = defaultdict(set)\n",
    "\n",
    "        for p, c in prerequisites:\n",
    "            d1[c].add(p)\n",
    "            d2[p].add(c)\n",
    "        \n",
    "        @lru_cache(None)\n",
    "        def search(c, p):\n",
    "            if p in d1[c]:\n",
    "                return True\n",
    "            \n",
    "            for c1 in d1[c]:\n",
    "                if search(c1, p):\n",
    "                    return True\n",
    "            \n",
    "            return False\n",
    "\n",
    "        ans = []\n",
    "        for p, c in queries:\n",
    "            ans.append(search(c, p))\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:\n",
    "        adj = defaultdict(set)\n",
    "        adj_pre = defaultdict(set)\n",
    "        for a, b in prerequisites:\n",
    "            adj[a].add(b)\n",
    "            adj_pre[b].add(a)\n",
    "\n",
    "        @cache\n",
    "        def query(x, y) -> bool:\n",
    "            if y in adj_pre[x]:\n",
    "                return False\n",
    "            if y in adj[x]:\n",
    "                return True\n",
    "            if any(query(z, y) for z in adj[x]):\n",
    "                adj[x].add(y)\n",
    "                return True\n",
    "            return False\n",
    "\n",
    "        return list(query(a, b) for a, b in queries)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:\n",
    "        edge = collections.defaultdict(list)\n",
    "        for info in prerequisites:\n",
    "            edge[info[1]].append(info[0])\n",
    "        res = []\n",
    "        save = {}\n",
    "        def check(course1, course2):\n",
    "            if ((course1, course2) in save):\n",
    "                return save[course1, course2]\n",
    "            if (course2 in edge[course1]):\n",
    "                save[(course1, course2)] = True\n",
    "                return True\n",
    "            else:\n",
    "                for p in edge[course1]:\n",
    "                    if check(p, course2):\n",
    "                        save[(course1, course2)] = True\n",
    "                        return True\n",
    "            save[(course1, course2)] = False\n",
    "            return False\n",
    "            \n",
    "        for q in queries:\n",
    "            label = check(q[1], q[0])\n",
    "            res.append(label)\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:\n",
    "        g = [[] for _ in range(numCourses)]\n",
    "        for f, t in prerequisites:\n",
    "            g[t].append(f)\n",
    "\n",
    "        @cache\n",
    "        def dfs(a, b):\n",
    "            if a == b:\n",
    "                return True\n",
    "            for nxt in g[b]:\n",
    "                if dfs(a, nxt):\n",
    "                    return True\n",
    "            return False\n",
    "\n",
    "        ans = []\n",
    "        for a, b in queries:\n",
    "            ans.append(dfs(a, b))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:\n",
    "\n",
    "        dp=dict()\n",
    "        grap=[[] for i in range(numCourses)]\n",
    "        for x,y in prerequisites:\n",
    "            grap[x].append(y)\n",
    "\n",
    "        def f(x,y):\n",
    "            if((x,y)) in dp:\n",
    "                return dp[(x,y)]\n",
    "            nex=grap[x]\n",
    "            if y in nex:\n",
    "                dp[(x,y)]=True\n",
    "                return True\n",
    "            for p in nex:\n",
    "                if f(p,y):\n",
    "                    dp[(x,y)]=True\n",
    "                    return True\n",
    "            dp[(x,y)]=False\n",
    "            return False\n",
    "        ans=[]\n",
    "        for x,y in queries:\n",
    "            ans.append(f(x,y))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:\n",
    "        from collections import defaultdict\n",
    "        dic = defaultdict(set)\n",
    "        for i,j in prerequisites:\n",
    "            dic[i].add(j)\n",
    "        # print(dic)\n",
    "        memo = {} #字典\n",
    "\n",
    "        def dfs(i,j):\n",
    "            if (i,j) in memo:\n",
    "                return memo[i,j]\n",
    "            post = False\n",
    "            if j in dic[i]:\n",
    "                post = True\n",
    "            else:\n",
    "                for k in dic[i]:\n",
    "                    if dfs(k,j):\n",
    "                        post = True\n",
    "                        break\n",
    "            memo[i,j] = post\n",
    "            # print(memo)\n",
    "            return post\n",
    "        return [dfs(i,j) for i,j in queries]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:\n",
    "        d = {}\n",
    "        res = []\n",
    "        for i,j in prerequisites:\n",
    "            if i in d:\n",
    "                d[i].append(j)\n",
    "            else:\n",
    "                d[i] = [j]\n",
    "\n",
    "        @cache\n",
    "        def dfs(x, y):\n",
    "            if not d.get(x):\n",
    "                return False\n",
    "            elif y in d.get(x):\n",
    "                return True\n",
    "            else:\n",
    "                for a in d.get(x):\n",
    "                    if dfs(a, y):\n",
    "                        return True\n",
    "                return False\n",
    "\n",
    "        for i,j in queries:\n",
    "            res.append(dfs(i, j))\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__(self, idx):\n",
    "        self.idx = idx\n",
    "        self.parents = {}\n",
    "        self.childs = {}\n",
    "\n",
    "class Solution:\n",
    "    def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:\n",
    "        g = {}\n",
    "        for i in range(numCourses):\n",
    "            g[i] = Node(i)\n",
    "        \n",
    "        visited = {}\n",
    "        def propagate_backwards(node_idx, new_child_idx):\n",
    "            if visited.get((node_idx, new_child_idx)) != None:\n",
    "                return\n",
    "    \n",
    "            node = g[node_idx]\n",
    "\n",
    "            for p_idx in node.parents:\n",
    "                p_node = g[p_idx]\n",
    "                p_node.childs[new_child_idx] = True\n",
    "                propagate_backwards(p_idx, new_child_idx)\n",
    "                visited[(p_idx, new_child_idx)] = True\n",
    "        \n",
    "        for itm in prerequisites:\n",
    "            A, B = itm\n",
    "            node_B = g[B]\n",
    "            node_B.parents[A] = True\n",
    "\n",
    "        for i in range(numCourses):\n",
    "            propagate_backwards(i, i)\n",
    "        \n",
    "        answers = []\n",
    "        for itm in queries:\n",
    "            A, B = itm\n",
    "            node_A = g[A]\n",
    "            if node_A.childs.get(B) != None:\n",
    "                answers.append(True)\n",
    "            else:\n",
    "                answers.append(False)\n",
    "    \n",
    "        return answers\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:\n",
    "        from collections import defaultdict\n",
    "        dic = defaultdict(set)\n",
    "        for i,j in prerequisites:\n",
    "            dic[i].add(j)\n",
    "        memo = {}\n",
    "\n",
    "        def dfs(i,j):\n",
    "            if (i,j) in memo:\n",
    "                return memo[i,j]\n",
    "            post = False\n",
    "            if j in dic[i]:\n",
    "                post = True\n",
    "            else:\n",
    "                for k in dic[i]:\n",
    "                    if dfs(k,j):\n",
    "                        post = True\n",
    "                        break\n",
    "            memo[i,j] = post\n",
    "            return post\n",
    "        return [dfs(i,j) for i,j in queries]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:\n",
    "        dic=dict()\n",
    "        for i in range( numCourses):\n",
    "            dic[i]=set()\n",
    "        for i in  prerequisites:\n",
    "            s=dic.get(i[1],set())\n",
    "            s.add(i[0])\n",
    "            dic[i[1]]=s\n",
    "        memo=dict()\n",
    "        def find(father,son):\n",
    "            if (father,son) in memo:\n",
    "                return memo[(father,son)]\n",
    "            if father in dic[son]:\n",
    "                memo[(father,son)]=True\n",
    "                return True\n",
    "            else:\n",
    "                for i in dic[son]:\n",
    "                    if find(father,i)==True:\n",
    "                        memo[(father,son)]=True\n",
    "                        return True\n",
    "            memo[(father,son)]=False\n",
    "            return False\n",
    "        ans=[]\n",
    "        for i in queries:\n",
    "            ans.append(find(i[0],i[1]))\n",
    "        return ans\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:\n",
    "        adj = [[] for _ in range(numCourses)]\n",
    "        for a, b in prerequisites:\n",
    "            adj[a].append(b)\n",
    "        \n",
    "        @cache\n",
    "        def dfs(u, v):\n",
    "            if v in adj[u]:\n",
    "                return True\n",
    "            for t in adj[u]:\n",
    "                if dfs(t, v):\n",
    "                    return True\n",
    "            return False\n",
    "        \n",
    "        return [dfs(u, v) for u, v in queries] "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:\n",
    "        # PRER = defaultdict(set)\n",
    "        # for x,y in prerequisites:\n",
    "        #     PRER[x].add(y)\n",
    "        \n",
    "        # def check_p(a,b):\n",
    "        #     return b in PRER[a] or any(check_p(k,b) for k in PRER[a])\n",
    "        # return [check_p(x, y) for x, y in queries]\n",
    "\n",
    "        mp = defaultdict(set)\n",
    "        for x, y in prerequisites:\n",
    "            mp[x].add(y)\n",
    "        \n",
    "        @cache\n",
    "        def dfs(x: int, y: int) -> bool:\n",
    "            return y in mp[x] or any(dfs(k, y) for k in mp[x])\n",
    "        \n",
    "        return [dfs(x, y) for x, y in queries]   \n",
    "        \n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__(self, val):\n",
    "        self.val = val\n",
    "        self.parents = set()\n",
    "    \n",
    "    def add(self, parent):\n",
    "        self.parents.add(parent)\n",
    "\n",
    "class Solution:\n",
    "    def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:\n",
    "        nodeMap = {}\n",
    "        for i in range(numCourses):\n",
    "            nodeMap[i] = Node(i)\n",
    "        for pre in prerequisites:\n",
    "            if pre[1] not in nodeMap:\n",
    "                nodeMap[pre[1]] = Node(pre[1])\n",
    "            if pre[0] not in nodeMap:\n",
    "                nodeMap[pre[0]] = Node(pre[0])\n",
    "            \n",
    "            nodeMap[pre[1]].add(pre[0])\n",
    "        \n",
    "        @cache\n",
    "        def dfs(cur, target):\n",
    "            if cur == target:\n",
    "                return True\n",
    "            node = nodeMap[cur]\n",
    "            for parent in node.parents:\n",
    "                if dfs(parent, target):\n",
    "                    return True\n",
    "            return False\n",
    "\n",
    "        res = []\n",
    "        for query in queries:\n",
    "            res.append(dfs(query[1], query[0]))\n",
    "        \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:\n",
    "\n",
    "        dp=dict()\n",
    "        grap=[[] for i in range(numCourses)]\n",
    "        for x,y in prerequisites:\n",
    "            grap[x].append(y)\n",
    "        @cache\n",
    "        def f(x,y):\n",
    "            nex=grap[x]\n",
    "            if y in nex:\n",
    "                return True\n",
    "            for p in nex:\n",
    "                if f(p,y):\n",
    "                    return True\n",
    "            return False\n",
    "        ans=[]\n",
    "        for x,y in queries:\n",
    "            ans.append(f(x,y))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:\n",
    "        s = defaultdict(set)\n",
    "        for pre, after in prerequisites:\n",
    "            s[pre].add(after)\n",
    "        @cache\n",
    "        def dfs(x: int, y: int) -> bool:\n",
    "            return y in s[x] or any(dfs(k, y) for k in s[x])\n",
    "        \n",
    "        return [dfs(x, y) for x, y in queries]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:\n",
    "\n",
    "        #ans = [False]*len(queries)\n",
    "        edges = defaultdict(list)\n",
    "        for x, y in prerequisites:\n",
    "            edges[x].append(y)\n",
    "\n",
    "        @cache\n",
    "        def dfs(x, y):\n",
    "            return y in edges[x] or any(dfs(k,y) for k in edges[x])\n",
    "        return [dfs(x, y) for x , y in queries]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:\n",
    "        mp = defaultdict(set)\n",
    "        for x, y in prerequisites:\n",
    "            mp[x].add(y)\n",
    "        \n",
    "        @cache\n",
    "        def dfs(x: int, y: int) -> bool:\n",
    "            return y in mp[x] or any(dfs(k, y) for k in mp[x])\n",
    "        \n",
    "        return [dfs(x, y) for x, y in queries]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:\n",
    "        mp = defaultdict(set)\n",
    "        for x, y in prerequisites:\n",
    "            mp[x].add(y)\n",
    "        \n",
    "        @cache\n",
    "        def dfs(x: int, y: int) -> bool:\n",
    "            return y in mp[x] or any(dfs(k, y) for k in mp[x])\n",
    "        \n",
    "        return [dfs(x, y) for x, y in queries]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:\n",
    "        mp = defaultdict(set)\n",
    "        for x, y in prerequisites:\n",
    "            mp[x].add(y)\n",
    "        \n",
    "        @cache\n",
    "        def dfs(x: int, y: int) -> bool:\n",
    "            return y in mp[x] or any(dfs(k, y) for k in mp[x])\n",
    "        \n",
    "        return [dfs(x, y) for x, y in queries]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:\n",
    "        mp = defaultdict(set)\n",
    "        for x, y in prerequisites:\n",
    "            mp[x].add(y)\n",
    "        \n",
    "        @cache\n",
    "        def dfs(x: int, y: int) -> bool:\n",
    "            return y in mp[x] or any(dfs(k, y) for k in mp[x])\n",
    "        \n",
    "        return [dfs(x, y) for x, y in queries]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def checkIfPrerequisite_v1(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:\n",
    "        adj_matrix = [[0 for _ in range(numCourses)] for _ in range(numCourses)]\n",
    "        for node_in, node_out in prerequisites:\n",
    "            adj_matrix[node_in][node_out] = 1\n",
    "        \n",
    "        @cache\n",
    "        def dfs(start, end):\n",
    "            if start == end:\n",
    "                return True\n",
    "\n",
    "            adj_nodes = [node for node, is_adj in enumerate(adj_matrix[start]) if is_adj == 1]\n",
    "            if len(adj_nodes) == 0:\n",
    "                return False\n",
    "            return any(dfs(nxt, end) for nxt in adj_nodes)\n",
    "        return [dfs(*q) for q in queries]\n",
    "\n",
    "    def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:\n",
    "        # 拓扑排序超时\n",
    "\n",
    "        adj_list = [set() for _ in range(numCourses)]  # 邻接表\n",
    "        indegrees = [0 for _ in range(numCourses)]  # 入度表\n",
    "\n",
    "        for node_in, node_out in prerequisites:\n",
    "            indegrees[node_out] += 1\n",
    "            adj_list[node_in].add(node_out)\n",
    "        \n",
    "        que = deque([node for node, indegree in enumerate(indegrees) if indegree == 0])\n",
    "        request = [set() for _ in range(numCourses)]  # 先修课程表\n",
    "        while len(que) != 0:\n",
    "            node = que.popleft()\n",
    "            for adj_node in adj_list[node]:\n",
    "                indegrees[adj_node] -= 1\n",
    "                request[adj_node].add(node)\n",
    "                if indegrees[adj_node] == 0:\n",
    "                    que.append(adj_node)\n",
    "        \n",
    "        @cache\n",
    "        def dfs(start, end):  # 判断start到end是否可达\n",
    "            if start == end:\n",
    "                return True\n",
    "            next_nodes = request[start]\n",
    "            if len(next_nodes) == 0:\n",
    "                return False\n",
    "            return any(dfs(nxt, end) for nxt in next_nodes)\n",
    "\n",
    "        return [dfs(start, end) for end, start in queries]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]: \n",
    "\n",
    "\n",
    "        graph = [[] for _ in range(numCourses)]\n",
    "        for info in prerequisites:\n",
    "            graph[info[1]].append(info[0])\n",
    "        \n",
    "        memo = set()\n",
    "        def dfs(u, target):\n",
    "            if (u, target) in memo:\n",
    "                return False\n",
    "            if u == target:\n",
    "                return True\n",
    "            for pre in graph[u]:\n",
    "                if dfs(pre, target):\n",
    "                    return True\n",
    "            memo.add((u, target))\n",
    "            return False\n",
    "        \n",
    "        answer = []\n",
    "        for info in queries:\n",
    "            if dfs(info[1], info[0]):\n",
    "                answer.append(True)\n",
    "            else:\n",
    "                answer.append(False)\n",
    "        \n",
    "        return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:\n",
    "        wcc=collections.defaultdict(set)\n",
    "        ans=[]\n",
    "        for i,j in prerequisites:\n",
    "            wcc[i].add(j)\n",
    "        # return wcc\n",
    "        @cache\n",
    "        def dfs(start,end,flag):\n",
    "            if start==end:\n",
    "                return True\n",
    "            for j in wcc[start]:\n",
    "                # return [j,end]\n",
    "                flag=flag or dfs(j,end,flag)\n",
    "                # return [j,end]\n",
    "            return flag\n",
    "            # return False\n",
    "        # return [dfs(0,3,False)]\n",
    "        for i in queries:\n",
    "            ans.append(dfs(i[0],i[1],False))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:\n",
    "        @cache\n",
    "        def dfs(cur, j):\n",
    "            if cur==j:\n",
    "                return True\n",
    "            \n",
    "            for i in range(numCourses):\n",
    "                if graph[cur][i] == 1:\n",
    "                    if dfs(i,j):\n",
    "                        return True\n",
    "            return False\n",
    "\n",
    "        # m = len(numCourses)\n",
    "        graph = [[0 for _ in range(numCourses)] for _ in range(numCourses)]\n",
    "\n",
    "        for x,y in prerequisites:\n",
    "            graph[x][y] = 1\n",
    "\n",
    "        res=[]\n",
    "        for x,y in queries:\n",
    "            res.append(dfs(x, y))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:\n",
    "        graph = defaultdict(set)\n",
    "        for u, v in prerequisites:\n",
    "            graph[u].add(v)\n",
    "        \n",
    "        @cache\n",
    "        def dfs(root, target):\n",
    "            if root == target:\n",
    "                return True\n",
    "            neighbors = graph[root]\n",
    "            for it in neighbors:\n",
    "                if dfs(it, target):\n",
    "                    return True\n",
    "            return False\n",
    "        \n",
    "        result = list()\n",
    "        for u, v in queries:\n",
    "            result.append(dfs(u, v))\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[\n",
    "        bool]:\n",
    "        lesson = defaultdict(set)\n",
    "        for prerequisite in prerequisites:\n",
    "            lesson[prerequisite[1]].add(prerequisite[0])\n",
    "\n",
    "        @lru_cache(maxsize=None)\n",
    "        def findAllPre(x: int, y: int) -> bool:\n",
    "            return x in lesson[y] or any(findAllPre(x, y) for y in lesson[y])\n",
    "\n",
    "        return [findAllPre(x, y) for x, y in queries]"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
